import java.util.Comparator;
import java.util.PriorityQueue;


class Imp implements Comparator<Integer>{

    @Override
    public int compare(Integer o1, Integer o2) {
//        降序排列   创建大根堆
        return o2.compareTo(o1);
    }

}
public class Test {

    public static void main(String[] args) {
        int[] arr = {27,15,19,18,28,34,65,49,25,37};
        TestHeap testHeap = new TestHeap();
        testHeap.heapSort(arr);
//        打印桶排序
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void main2(String[] args) {
//        使用优先级队列
//        说明优先级队列创建的是小根堆
        PriorityQueue<Student> priorityQueue = new PriorityQueue<>();
//        priorityQueue.offer(1);
//        priorityQueue.add(5);
//        priorityQueue.add(6);
//        priorityQueue.add(34);
//        priorityQueue.add(3);

//        priorityQueue.offer(null);   不让插入null的对象
        priorityQueue.offer(new Student(12,"zhang san"));
//        priorityQueue.offer(new Student(15,"zhan gan"));
        System.out.println(priorityQueue.peek());


    }

    // 这种求Top-K 问题 往往数据量很大 而所求的数字不大
    public int[] smallestK(int[] arr, int k) {
//        因此采用以下方式复杂度会变低
//        1. 根据 K 创建大根堆  从 K+1 元素开始依次比较 如果比堆顶元素小 则入堆 然后向下调整 遍历到最后
        Imp imp = new Imp();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(imp);
        // 创建大根堆的 Comparator
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
//            剩下的元素与我的大根堆的堆顶元素比较 如果小 则入堆调整
            int top = priorityQueue.peek();
            if (arr[i] < top){
//                入堆
               priorityQueue.poll();//将堆顶元素直接弹出
                priorityQueue.offer(arr[i]);
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
       return ret;
    }



    public static void main1(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] arr = {27,15,19,18,28,34,65,49,25,37};
        //        初始化大根堆
        testHeap.initElem(arr);

//        创建大跟堆
        testHeap.createMaxHeap();
        testHeap.printHeap();

//        向堆中添加元素
        testHeap.insert(99);
        testHeap.printHeap();

//        删除堆顶元素
        testHeap.delete();
        testHeap.printHeap();

    }
}
